#include "PriorityHeap.h"
#include <stdexcept>

template <class Comparable>
BinaryHeap<Comparable>::BinaryHeap(int capacity)
						  : currentSize(0), capacity(capacity)
{ 
	array.reserve(capacity);	
}

template <class Comparable>
bool BinaryHeap<Comparable>::isFull() const
{
	return currentSize == capacity;
}

template <class Comparable>
bool BinaryHeap<Comparable>::isEmpty() const
{
	return currentSize == 0;
}

template <class Comparable>
void BinaryHeap<Comparable>::insert(const Comparable &x)
{
	if (isFull())
		range_error("out of range");
	
	int hole = ++currentSize;
	for (; hole > 1 && x < array[hole/2]; hole /= 2)
		array[hole] = array[hole/2];
	array[hole] = x;
}

template <class Comparable>
void BinaryHeap<Comparable>::deleteMin(Comparable &minItem) 
{
	if (isEmpty())
		range_error("heap empty");
	
	minItem = array[1];
	array[1] = array[currentSize--];
	percolateDown(1);
}

template <class Comparable>
void BinaryHeap<Comparable>::deleteMin() 
{
	if (isEmpty())
		range_error("heap empty");
	
	Comparable &minItem = array[1];
	array[1] = array[currentSize--];
	percolateDown(1);
}

template <class Comparable>
void BinaryHeap<Comparable>::makeEmpty()
{
	currentSize = 0;
}

template <class Comparable>
const Comparable & 
BinaryHeap<Comparable>::findMin() const
{
	return array[1];
}


template <class Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole) 
{
	int child;
	Comparable tmp = array[hole];

	for (; hole * 2 <= currentSize; hole = child) {
		child = hole * 2;
		if (child != currentSize && array[child + 1] < array[child])
			child++;
		if (array[child] < tmp)
			array[hole] = array[child];
		else 
			break;
	}
	array[hole] = tmp;
}

template <class Comparable>
void BinaryHeap<Comparable>::buildHeap()
{
	for (int i = currentSize/2; i > 0; i--)	
		percolateDown(i);
}

template <class Comparable>
Comparable & BinaryHeap<Comparable>::operator[](const int i)
{
	return array[i];
}

